package com.algorithm.sort;

import java.util.Arrays;

public class InsertSort {

	public static void main(String args[]){
		int [] array = new int[]{20,12,332,212,23,4533,2,23,4,532,245,342,22,442,32,442,21,2,34,35,32,123,1234,2323,132322};
		insertionSort(array);
	}


	/*简单插入排序 类似于拿扑克*/
	private static void insertSort(int [] array){

		int arraySortEd [] = new int[array.length];

		for(int i = 0;i<array.length;i++){
			int tempI = array[i];
			if(i==0){
				arraySortEd[0] = tempI;
			}else{
				for(int j=i-1;j>=0;j--){
					int tempj = arraySortEd[j];
					//待插入的位置
					if(tempI < tempj){
						resortSize(arraySortEd,i,tempI);
						break;
					}else{
						arraySortEd[i] = tempI;
						break;
					}
				}
			}
			System.out.println(Arrays.toString(arraySortEd));
		}

	}

	/*插入排序 判断当前应该插入的位置规则*/
	private static void resortSize(int array[], int xPos,int data){
		int beginPosition = 0;
		for(int i =0 ;i<xPos;i++){
			if(array[i]>data){
				beginPosition = i;
				break;
			}
		}

		int tempData = 0;
		for(int i = beginPosition;i<xPos+1;i++){
			if(i == beginPosition){
				tempData = array[i];
			   array[i] = data;
			}else{
				int tempCurrent =  array[i];
				array[i] = tempData;
				tempData = tempCurrent;
			}
		}
	}


//	function insertionSort(arr) {
//
//		var len = arr.length;
//
//		var preIndex, current;
//
//		for (var i = 1; i < len; i++) {
//
//			preIndex = i - 1;
//
//			current = arr[i];
//
//			while (preIndex >= 0 && arr[preIndex] > current) {
//
//				arr[preIndex + 1] = arr[preIndex];
//
//				preIndex--;
//
//			}
//
//			arr[preIndex + 1] = current;
//
//		}
//
//		return arr;
//
//	}
	private static void insertionSort(int array[]){
		int preIndex = 0,current= 0;
		for(int i = 1;i< array.length;i++){
			preIndex = i-1;
			current = array[i];
			//这里做移动工作，移动到最后 倒数最后一位 -1的值被覆盖，后续用current这个变量替换
			while(preIndex>=0&&current<array[preIndex]){
				array[preIndex + 1] = array[preIndex];
				preIndex--;
			}
			array[preIndex + 1] = current;
			System.out.println(Arrays.toString(array));
		}
	}
}
